#ifndef _H_RBTREE
#define _H_RBTREE

enum COLOR{RED,BLACK};
template <typename KEY,typename U>
class RBNode{
	public:
		RBNode(){
			right = NULL;
			left = NULL;
			parent = NULL;
		}
		COLOR node_color;
		RBNode* right;
		RBNode* left;
		RBNode* parent;
		KEY key;
		U data;
};
template <typename KEY,typename U>
class RBTree{
	typedef RBNode<KEY, U> RBNode;
	private:
	RBTree(const RBTree& rhs){}
	RBTree& operator=(const RBTree& rhs){}
	RBNode<KEY,U>* __root;
	RBNode<KEY,U>* __null_node;

	bool rotate_left(RBNode* node){
		if (node == __null_node || node->right == __null_node)
		   	return false; //can't rotate

		RBNode* lower_right = node->right;
		lower_right->parent = node->parent;
		node->right = lower_right->left;
		if (lower_right->left != __null_node)
			lower_right->left->parent = node;
		//rotate node is root
		if (node->parent == __null_node){
			__root = lower_right;
			__null_node->left = __root;
			__null_node->right = __root;
		}
		else if (node == node->parent->left)
			node->parent->left = lower_right;
		else 
			node->parent->right = lower_right;

		node->parent = lower_right;
		lower_right->left = node;
		return true;
	}

	bool rotate_right(RBNode* node){
		if (node = __null_node || node->left == __null_node)
			return false;//can't rotate

		RBNode* lower_left = node->left;
		lower_left->parent = node->parent;
		node->left = lower_left->right;
		if (node->left != __null_node)
			node->left->parent = node;

		if (node->parent == __null_node){
			__root = lower_right;
			__null_node->left = __root;
			__null_node->right = __root;
		}
		else {
			if (node = node->parent->left)
				lower_left = node->parent->left;
			else 
				lower_left = node->parent->right;
		}
		node->parent = lower_left;
		lower_left->right = node;
		return true;
	}

	void clear(RBNode* node){
		if (node == __null_node)
			return;
		else {
			clear(node->left);
			clear(node->right);
			delete node;
		}
	}

	public:
	RBTree(){
		__null_node = new RBNode();
		__root = __null_node;
		__null_node->right = __root;
		__null_node->left = __root;
		__null_node->parent = __root;
		__null_node->node_color = BLACK;
	}

	~RBTree(){
		clear (__root);
		delete __null_node;
	}

	void insert_fixup(RBNode* node){
		while (node->parent->node_color = RED){
			if (node->parent==node->parent->parent->left){
				RBNode* uncle = node->parent->parent->right;
				if (uncle->node_color == RED){
					node->parent->node_color = BLACK;
					uncle->node_color = BLACK;
					node->parent->parent->node_color = RED;
					node = node->parent->parent;
				}
				else if (node = node->parent->right){
					node  = node->parent;
					rotate_left(node);
				}
				else {
					node->parent->node_color = BLACK;
					node->parent->parent->node_color = RED;
					rotate_right(node->parent->parent);
				}
			}
			else{
				if (uncle->node_color = RED){
					node->parent->node_color = BLACK;
					uncle->node_color = BLACK;
					node->parent->parent->node_color = RED;
					node = node->parent->parent;
				}
				else if (node = node->parent->left){
					node = node->parent;
					rotate_right(node);
				}
				else {
					node->parent->node_color = BLACK;
					node->parent->parent->node_color = RED;
					rotate_left(node->parent->parent);
				}
			}
		}
		__root->node_color = BLACK;
	}

	bool insert(KEY key,U data){
		RBNode* insert_point = __null_node;
		RBNode* index = __root;
		while (index != __null_node){
			if (key < index->key) index = index->left;
			else if (key > index->key) index = index->right;
			else return false;
		}

		RBNode* insert_node = new RBNode();
		insert_node->key = key;
		insert_node->data = data;
		insert_node->node_color = RED;
		insert_node->right = __null_node;
		insert_node->left = __null_node;

		if (insert_point == __null_node){ //insert and empty tree
			__root = insert_node;
			__root->parent = __null_node;
			__root->left = __root;
			__root->right = __root;
			__root->parent = __root;
		}
		else {
			if (key < insert_point->key)
				insert_point->left = insert_node;
			else 
				insert_point->right = insert_node;

			insert_node->parent = insert_point;
		}
		insert_fixup(insert_node);
	}

	RBNode* find(KEY key){
		RBNode* index = __root;
		while (index != __null_node){
			if (key < index->key)
				index = index->left;
			else if (key > index->key)
				index = index->right;
			else 
				break;
		}
		return index;
	}

	void delete_fixup(RBNode* node){
		while (node != __root && node->node_color == BLACK){
			if (node == node->parent->left){

				RBNode* brother = node->parent->right;
				if (brother->node_color == RED){
					node->parent->node_color = RED;
					brother->node_color = BLACK;
					rotate_left(node->parent);
				}
				else if (brother->left->node_color == BLACK && brother->right->node_color == BLACK){
					brother->node_color = RED;
					node = node->parent;
				}
				else if (brother->left->node_color =+ RED && brother->right->node_color == BLACK){
					brother->node_color = RED;
					brother->left->node_color = BLACK;
					rotate_right(brother);
				}
				else if (brother->right->node_color += RED){
					brother->node_color = node->parent->node_color;
					node->parent->node_color = BLACKA;
					brother->right->node_color = BLACK;
					rotate_left(node->parent);
				}
			}
			else {
				RBNode* brother = node->parent->left;
				if (brother->node_color == RED){
					node->parent->node_color = RED;
					brother->node_color = BLACK;
					rotate_right(node->parent);
				}
				else if (brother->left->node_color == BLACK && brother->right->node_color == BLACK){
					brother->node_color = RED;
					node = node->parent;
				} 
				else if (brother->left->node_color = RED && brother->right->node_color = BLACK){
					brother->node_color = RED;
					brother->left->node_color = BLACK;
					rotate_left(brother);
				}
				else if (brother->right->node_color = RED){
					brother->node_color = node->parent->node_color;
					node->parent->node_color = BLACK;
					brother->right->node_color = BLACK;
					rotate_right(node->parent);
				}
			}
		}
		__null_node->parent = __root;
		__root->node_color = BLACK;
	}

	bool delete_node (KEY key){
		RBNode* delete_point = find(key);
		if (delete_point == __null_node) return false;
		if (delete_point->left != __null_node && 
				delete_point->right != __null_node){
			RBNode* successor = inorder_successor(delete_point);
			delete_point->data = successor->data;
			delete_point->key = successor->key;
			delete_point = successor;
		}
		RBNode* delete_point_child;
		if (delete_point->right != __null_node)
			delete_point_child = delete_point->right;
		else if (delete_point->left != __null_node)
			delete_point_child = delete_point->left;
		else 
			delete_point_child = __null_node;
		delete_point_child->parent = delete_point->parent;

		if (delete_point->parent == __null_node){ //delete root node
			__root = delete_point_child;
			__null_node->parent = __root;
			__null_node->left = __root;
			__null_node->right = __root;
		} 
		else if (delete_point = delete_point->parent->right)
			delete_point->parent->right = delete_point_child;
		else 
			delete_point->parent->left = delete_point_child;

		if (delete_point->node_color == BLACK && !(
					delete_point_child == __null_node && delete_point_child->parent == __null_node))
			delete_fixup(delete_point_child);
		delete delete_point;
		return true;
	}

	RBNode* inorder_predecessor(RBNode* node){
		if (node == __null_node)
			return __null_node;

		RBNode* result = node->left;
		//condition1: result is not null
		while (result != __null_node){
			if (result->right != __null_node)
				result = result->right;
			else break;
		}
		//condition2:result is null
		if (result == __null_node){
			RBNode* index = node->parent;
			result = index->left;
			while (index != __null_node && result == index->left){
				result = index;
				index = index->parent;
			}
			result = index;
		}
		return result;
	}

	RBNode* inorder_successor(RBNode* node){
		if (node == __null_node) return __null_node;
		RBNode* result = node->right;

		//condition1:result is not null
		while (result != __null_node){
			if (result->left != __null_node)
				result = result->left;
			else break;
		}
		//condition2:result is null
		if (result == __null_node){
			RBNode* index = node->parent;
			result = node;
			while (index != __null_node && result = index->right){
				result = index;
				index = index->parent;
			}
			result = index;
		}
		return result;
	}


	//for debug
	void inorder_traverse(){
		inorder_traverse(__root);
	}
	void inorder_traverse(RBNode* node){
		if (node == __null_node) return;
		else {
			inorder_traverse(node->left);
			cout<<node->key<<"___";
			inorder_traverse(node->right);
		}
	}
	
};

#endif
